#include <queue>
#include <tuple>

using namespace std;

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int count = 0;
        int step = 0;
        queue<tuple<int, int>> rot_pos;
        int height = grid.size();
        int width = grid[0].size();
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                if (grid[i][j] > 0) {
                    count++;
                }
                if (grid[i][j] == 2) {
                    rot_pos.push(make_tuple(i, j));
                }
            }
        }
        while (!rot_pos.empty()) {
            for (int k = 0, len = rot_pos.size(); k < len; k++) {
                tuple<int, int>& pos = rot_pos.front();
                int i = get<0>(pos);
                int j = get<1>(pos);
                if (i > 0 && grid[i - 1][j] == 1) {
                    grid[i - 1][j] = 2;
                    rot_pos.push(make_tuple(i - 1, j));
                }
                if (i < height - 1 && grid[i + 1][j] == 1) {
                    grid[i + 1][j] = 2;
                    rot_pos.push(make_tuple(i + 1, j));
                }
                if (j > 0 && grid[i][j - 1] == 1) {
                    grid[i][j - 1] = 2;
                    rot_pos.push(make_tuple(i, j - 1));
                }
                if (j < width - 1 && grid[i][j + 1] == 1) {
                    grid[i][j + 1] = 2;
                    rot_pos.push(make_tuple(i, j + 1));
                }
                rot_pos.pop();
                count--;
            }
            step++;
        }
        if (count > 0) {
            return -1;
        }
        return max(0, step - 1);
    }
};